#include <iostream>

int power_0(int a, int n) {
	if (n==1) return a;
	if (n%2 == 0)
		return power_0(a*a, n/2);
	else 
		return a * power_0(a*a, n/2);
}
//reduce the number of recursive calls, by common-subexpression elimination
int power_1(int a, int n) {
	if (n==1) return a;
	int r = power_1(a*a, n/2);
	if (n%2 ==1) 
		r *= a;
	return r;
}
//move the recursive call to the end , by introducing accumulation variable
int power_accumulate_0(int r, int a, int n){
	if (n==0) return r;
	if (n==1) return r*a;
	if (n%2 == 1) r *= a;
	return power_accumulate_0(r, a*a, n/2);
}
//slight improvement by eliminating common subexpression
int power_accumulate_1(int r, int a, int n){
	if (n%2 == 1) {
		r *= a;
		if(n==1)
			return r;
	}
	else {
		if(n==0)
			return r;
	}
	return power_accumulate_1(r,a*a,n/2);
}
//convert to strictly tail recursion by updating a and n outside the recursive call
int power_accumulate_2(int r, int a, int n){
	if (n%2 == 1) {
		r *= a;
		if(n==1)
			return r;
	}
	else {
		if(n==0)
			return r;
	}
	a *= a;
	n /= 2;
	return power_accumulate_2(r,a,n);
}

//n >= 0
//replace the tail recursive call by a while loop(goto to the beginning)
int power_accumulate_iterative_0(int r, int a, int n){
	while(true) {
		if (n%2 == 1) {
			r *= a;
			if(n==1)
				return r;
		}
		else {
			if(n==0)
				return r;
		}
		a *= a;
		n /= 2;
	}
}
//n > 0
//reduce the common step from n=1 to n=0
int power_accumulate_positive(int r, int a, int n){
	while(true) {
		if (n%2 == 1) {
			r *= a;
			if(n==1)
				return r;
		}
		a *= a;
		n /= 2;
	}
}
int power_accumulate_iterative_1(int r, int a, int n) {
	if(n==0) return r;
	return power_accumulate_positive(r,a,n);
}



void test_power(){
	int a,n;
	while(std::cin >> a && std::cin >>n){
		std::cout << a << '^' << n << " = "  << power_0(a,n) << std::endl;
		std::cout << a << '^' << n << " = "  << power_1(a,n) << std::endl;
		std::cout << a << '^' << n << " = "  << power_accumulate_0(1,a,n) << std::endl;
		std::cout << a << '^' << n << " = "  << power_accumulate_1(1,a,n) << std::endl;
		std::cout << a << '^' << n << " = "  << power_accumulate_2(1,a,n) << std::endl;
		std::cout << a << '^' << n << " = "  << power_accumulate_iterative_0(1,a,n) << std::endl;
		std::cout << a << '^' << n << " = "  << power_accumulate_iterative_1(1,a,n) << std::endl;
	}
}